<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Modelling MP problems in ECLiPSe
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial117.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial115.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial119.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc231">16.3</A>&nbsp;&nbsp;Modelling MP problems in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP></H2><UL>
<LI><A HREF="tutorial118.html#toc115">Eplex instance</A>
<LI><A HREF="tutorial118.html#toc116">Example modelling of an MP problem in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP></A>
<LI><A HREF="tutorial118.html#toc117">Getting more solution information from the solver</A>
<LI><A HREF="tutorial118.html#toc118">Adding integrality constraints</A>
</UL>

<A NAME="mpmodelling"></A>
<A NAME="toc115"></A>
<H3 CLASS="subsection"><A NAME="htoc232">16.3.1</A>&nbsp;&nbsp;Eplex instance</H3>
The simplest way to model an eplex problem is through an <I>eplex
instance</I>. Abstractly, it can be viewed as a solver module that is
dedicated to one MP problem. MP constraints can be posted to the instance 
and the problem solved with respect to an objective function by the
external solver.<BR>
<BR>
Declaratively, an eplex instance can be
seen as a compound constraint consisting of all the variables and
constraints of its eplex problem. Like normal constraints, different eplex
instances can share variables, although the individual MP constraints in
an eplex instance do not necessarily have to be consistent with those in
another. <BR>
<BR>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	<BR>
<BR>
An <B>eplex instance</B> represents a single MP problem in a
module. Constraints for the problem are posted to the module. The
problem is solved with respect to an objective function.

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 16.3: Eplex Instance</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<A NAME="toc116"></A>
<H3 CLASS="subsection"><A NAME="htoc233">16.3.2</A>&nbsp;&nbsp;Example modelling of an MP problem in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP></H3>
<A NAME="@default410"></A>
The following code models (and solves) the transportation problem of
Figure&nbsp;<A HREF="tutorial116.html#tpprob">16.2</A>, using an eplex instance:<BR>
<BR>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- lib(eplex).

:- eplex_instance(prob).  % a. declare an eplex instance

main1(Cost, Vars) :-
        % b. create the problem variables and set their range
        Vars = [A1,A2,A3,B1,B2,B3,C1,C2,C3,D1,D2,D3], 
        prob: (Vars $:: 0.0..1.0Inf),

        % c. post the constraints for the problem to the eplex instance
        prob: (A1 + A2 + A3 $= 21),
        prob: (B1 + B2 + B3 $= 40),
        prob: (C1 + C2 + C3 $= 34),
        prob: (D1 + D2 + D3 $= 10),

        prob: (A1 + B1 + C1 + D1 $=&lt; 50),
        prob: (A2 + B2 + C2 + D2 $=&lt; 30),
        prob: (A3 + B3 + C3 + D3 $=&lt; 40),

        % d. set up the external solver with the objective function
        prob: eplex_solver_setup(min(
                10*A1 + 7*A2 + 200*A3 + 
                 8*B1 + 5*B2 + 10*B3 +
                 5*C1 + 5*C2 +  8*C3 + 
                 9*D1 + 3*D2 +  7*D3)),

        %&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;- End of Modelling code

        prob: eplex_solve(Cost).  % e. Solve problem using external solver

</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
<BR>
To use an eplex instance, it must first be declared with <CODE>eplex_instance/1</CODE>. 
This is usually done with a directive, as in line <CODE>a</CODE>.
Once
declared, an eplex instance can be referred to using its name like a module
qualifier.<BR>
<BR>
We first create the problem
variables and set their range to be non-negative, as is conventional in MP.
Note that the bounds are posted to our eplex instance, using <CODE>$::/2</CODE>.

<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCFFCC">
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&otimes;</B><DD CLASS="dd-description"> The default bounds for variables is -1.0Inf..1.0Inf. Bounds posted to
 an eplex instance are specific to that eplex instance.
</DL>
</TD>
</TR></TABLE>
<BR>
Next, we set up the MP constraints for the
problem by posting them to the eplex instance. 
The MP constraints accepted by eplex are the arithmetic equalities and 
inequalities:
<CODE>$=/2</CODE>, <CODE>$=&lt;/2</CODE> and <CODE>$&gt;=/2</CODE>.

<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCFFCC">
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&otimes;</B><DD CLASS="dd-description"> The arithmetic constraints can be linear expressions on both
sides. The restriction to linear
expressions originates from the external solver.
</DL>
</TD>
</TR></TABLE>

<A NAME="@default411"></A>
<A NAME="@default412"></A>
<A NAME="@default413"></A>
<A NAME="@default414"></A>
<A NAME="@default415"></A>
<A NAME="@default416"></A><BR>
We need to setup the external solver with the eplex instance, so
that the problem can be solved by the external solver. This is done by
<CODE>eplex_solver_setup/1</CODE>, with the objective
function given as the argument, enclosed by either <CODE>min(...)</CODE> or <CODE>max(...)</CODE>. In this case, we are minimising.
Note that
generally the setup of the solver and the posting of the MP constraints can be
done in any order.<BR>
<BR>
Having set up the problem, we can solve it
by calling <CODE>eplex_solve/1</CODE> in line <CODE>e</CODE>. <BR>
<BR>
When an instance gets solved, the external solver takes into account all
constraints posted to that instance, the current variable bounds for the
problem variables, and the objective specified during setup.<BR>
<BR>
In this case, there is an optimal solution of 710.0:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?-  main1(Cost, Vars).

Cost = 710.0
Vars = [A1{0.0 .. 1e+20 @ 0.0}, A2{0.0 .. 1e+20 @ 21.0}, ....]
</PRE></BLOCKQUOTE>
Note that the problem variables are not
instantiated by the solver. However, the `solution' values, i.e. the
values that the variable are given by the solver, are available in the
eplex attribute. The eplex attribute is shown as <CODE>Lo..Hi @ Sol</CODE> where
<CODE>Lo</CODE> is the lower bound, <CODE>Hi</CODE> the upper bound, and <CODE>Sol</CODE> the
solution value for the variable (e.g., <CODE>A2</CODE> has the solution value of
21.0 in the example above). Note also that the external solver may not
allow very large floats, hence <CODE>1e+20</CODE>, this external solver's
representation of infinity, is the upper bound of the
variables, even though we specified <CODE>1.0Inf</CODE> in our code. <BR>
<BR>
One reason the problem variables are not assigned their solution values is
so that the eplex problem can be solved again, after it has been modified.
A problem can be modified by the addition of more constraints, and/or
changes in the bounds of the problem variables.<BR>
<BR>
<A NAME="toc117"></A>
<H3 CLASS="subsection"><A NAME="htoc234">16.3.3</A>&nbsp;&nbsp;Getting more solution information from the solver</H3>
The solution values of the problem variables can be obtained by
<CODE>eplex_var_get/3</CODE>. The example program in the
previous section can be modified to return the solution values:<BR>
<BR>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
main2(Cost, Vars) :-
        ....  % same as previous example up to line e
        prob: eplex_solve(Cost),  % e. Solve problem using external solver
        (foreach(V, Vars) do
            % f. set the problem variables to their solution values
            prob: eplex_var_get(V, typed_solution, V) 
        ).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
<A NAME="@default417"></A><BR>
In line <CODE>f</CODE>, <CODE>eplex_var_get/3</CODE> is used to obtain the solution
value for a problem variable. The second argument, set to <CODE>typed_solution</CODE>, 
 specifies that we want the solution value for the variable to be returned.
Here, we instantiate the problem variable itself to the solution value
with the third argument:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- main2(Cost, Vars).


Cost = 710.0
Vars = [0.0, 21.0, 0.0, 16.0, 9.0, 15.0, 34.0, 0.0, 0.0, 0.0, 0.0, 10.0]
</PRE></BLOCKQUOTE>
Note that, in general, an MP problem can have many optimal solutions, i.e.
different solutions which give the optimal value for the objective function.
As a result, the above
instantiations for <CODE>Vars</CODE> might not be what is returned by the solver
used.<BR>
<BR>
<A NAME="toc118"></A>
<H3 CLASS="subsection"><A NAME="htoc235">16.3.4</A>&nbsp;&nbsp;Adding integrality constraints</H3>
<A NAME="@default418"></A>
In general, a problem variable is not restricted to taking integer
values. However, for some problems, there may be a requirement that some or
all of the variable values be strictly integral (for example, in the previous
transportation problem, it may be that only whole units of the
products can be transported; also variables may often be used to model
booleans by allowing them to take on the values of 0 or 1 only). 
This can be specified by
posting an additional <CODE>integers/1</CODE> constraint on the
variables. <BR>
<BR>
<A NAME="@default419"></A>
Consider the example problem again, where it so happens that the
optimal value for the objective function can be satisfied with integral
values for the variables. To show the differences
that imposing integer constraints might make, we add the constraint that
client A must receive an equal amount of products from plants 1 and 2. Now
the problem (without the integer constraints) can be written as:<BR>
<BR>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- lib(eplex).

:- eplex_instance(prob).  

main3(Cost, Vars) :-
        Vars = [A1,A2,A3,B1,B2,B3,C1,C2,C3,D1,D2,D3], 
        prob: (Vars $:: 0.0..1.0Inf),
        prob: (A1 + A2 + A3 $= 21),
        prob: (B1 + B2 + B3 $= 40),
        prob: (C1 + C2 + C3 $= 34),
        prob: (D1 + D2 + D3 $= 10),

        prob: (A1 + B1 + C1 + D1 $=&lt; 50),
        prob: (A2 + B2 + C2 + D2 $=&lt; 30),
        prob: (A3 + B3 + C3 + D3 $=&lt; 40),

        prob: eplex_solver_setup(min(
                10*A1 + 7*A2 + 200*A3 + 
                 8*B1 + 5*B2 + 10*B3 +
                 5*C1 + 5*C2 +  8*C3 + 
                 9*D1 + 3*D2 +  7*D3)),

        prob: (A1 $= A2), % g. the new constraint, added after setup

        %&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;&mdash;- End of Modelling code

        prob: eplex_solve(Cost),  
        (foreach(V, Vars) do
            prob: eplex_var_get(V, typed_solution, V) 
        ).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
In this example, the new constraint in line <CODE>g</CODE> is imposed after the
solver setup. In fact it can be imposed anytime before
<CODE>eplex_solve(Cost)</CODE> is called.<BR>
<BR>
This problem also has an optimal <CODE>Cost</CODE> of 710, the same as the original
problem. However, the solution values are not integral:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- main3(Cost, Vars).

Cost = 710.0
Vars = [10.5, 10.5, 0.0, 5.5, 19.5, 15.0, 34.0, 0.0, 0.0, 0.0, 0.0, 10.0]
</PRE></BLOCKQUOTE>
Now, to impose the constraints that only whole units of the products can be
transported, we modify the program as follows:<BR>
<BR>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
main4(Cost, Vars) :-
        Vars = [A1,A2,A3,B1,B2,B3,C1,C2,C3,D1,D2,D3], 
        prob: (Vars $:: 0.0..1.0Inf),
        prob: integers(Vars),  % h. impose the integrality constraint
        ....% Rest is the same as main3
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
In line <CODE>h</CODE>, we added the <CODE>integers/1</CODE> constraint. This imposes
the integrality constraint on <CODE>Vars</CODE> for the eplex instance
<CODE>prob</CODE>. Now,
the external solver will only assign integer solution values to the
variables in the list. 
<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCFFCC">
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&otimes;</B><DD CLASS="dd-description"> In fact, with the integer
constraints, the problem is solved
as a MIP problem rather than an LP problem, which involves different
(and generally computationally more expensive) techniques. This difference
is hidden from the eplex user.
</DL>
</TD>
</TR></TABLE>
<BR>
Running this program, we get:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">

?- main4(Cost,Vars).

Cost = 898.0
Vars = [10, 10, 1, 6, 20, 14, 34, 0, 0, 0, 0, 10]

</PRE></BLOCKQUOTE>
In this case, <CODE>A1</CODE> and <CODE>A2</CODE> are now integers. In fact, notice
that all the values returned are now integers rather than floats. This is
because the <CODE>typed_solution</CODE> option of <CODE>eplex_var_get/3</CODE>
returns the solution values taking into account if the variables have been
declared as integers for the eplex instance.

<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCFFCC">
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&otimes;</B><DD CLASS="dd-description"> Posting an integers/1 constraint to an eplex instance only
 inform the external solver to treat those variables as integers (in fact
 the external solver will still represent the variables as floats, but
 will only assign intergral solution values to them), but does
 not constrain the variable itself to be of type integer.
</DL>
</TD>
</TR></TABLE>
<BR>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
<UL CLASS="itemize"><LI CLASS="li-itemize">
Declare an eplex instance using <B>eplex_instance(+Instance)</B>.
<LI CLASS="li-itemize">Post the constraints (<B>$=/2, $&gt;=/2, $=&lt;/2, integers/1,
 $::/2</B>) for the problem to the eplex instance.
<LI CLASS="li-itemize">Setup the solver with the objective function using<BR>
<B>Instance: eplex_solver_setup(+ObjFunc)</B>.
</UL>

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 16.4: Modelling an MP Problem</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<HR>
<A HREF="tutorial117.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial115.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial119.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
